package 分割等和子集;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/7 13:28
 * @description:
 */
public class Solution2 {
    public boolean canPartition(int[] nums) {
        // 采用回溯法
        // ① 回溯的参数和返回值；nums，target，int index, int[] bucket . 返回值：Boolean
        // ② 回溯的终止条件：index == nums.length
        // ③ 回溯搜索的逻辑：树的每一层理解为 nums[index] 进行选择，选择进入到 桶1 还是进入到 桶2。

        int sum = Arrays.stream(nums).sum();
        int target = sum / 2;
        if (sum % 2 != 0) return false;
        // 排序（防止重复）
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;
            r--;
        }
        return backTracking(nums, 0, target, new int[2]);
    }

    public boolean backTracking(int[] nums, int index, int target, int[] bucket) {
        if (index == nums.length) {
//            System.out.println(Arrays.toString(bucket));
//            for (int localSum : bucket) {
//                if (localSum != target) return false;
//            }
            return true;
        }

        for (int i = 0; i < 2; i++) {
            // 减枝
            if (bucket[i] + nums[index] > target) continue;
            if (i == 1 && bucket[0] == bucket[1]) continue;
            bucket[i] += nums[index];
//            System.out.println("index:" + index);
            if (backTracking(nums, index + 1, target, bucket)) return true;
            // 回溯
            bucket[i] -= nums[index];
        }

        return false;

    }
}
